package leetcode.tree;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}


public class Lc1367 {

    public boolean isSubPath(ListNode head, TreeNode root) {
        if (root == null) return false;
        //递归：就是枚举二叉树中所有的点作为头节点与head链表进行匹配
        //return dfs(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);

        //另外一种非递归的写法
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) { //tree中的每一个节点依次进队，然后与链表进行匹配
            TreeNode node = queue.poll();
            if (dfs(head, node)) return true;
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        return false;
    }

    private boolean dfs(ListNode head, TreeNode root) {

        if (head == null) return true;
        if (root == null) return false;
        if (head.val != root.val) return false;
        return dfs(head.next, root.left) || dfs(head.next, root.right);
    }


}
